1209. Remove All Adjacent Duplicates in String II
Medium

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

 

Example 1:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

Example 2:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"

 

Constraints:

  • 1 <= s.length <= 105
  • 2 <= k <= 104
  • s only contains lower case English letters.
Accepted
105,165
Submissions
184,381
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
Use a stack to store the characters, when there are k same characters, delete them.
Show Hint 2
To make it more efficient, use a pair to store the value and the count of each character.

Average Rating: 4.66 (44 votes)

Premium

Solution


Approach 1: Brute Force

We can do exactly what the problem asks: count repeating adjacent letters and remove them when the count reaches k. Then, we do it again until there is nothing to remove.

Brute Force Illustration

Algorithm

  1. Remember the length of the string.

  2. Iterate through the string:

    • If the current character is the same as the one before, increase the count.

      • Otherwise, reset the count to 1.
    • If the count equals k, erase last k characters.

  3. If the length of the string was changed, repeat starting from the first step.

Complexity Analysis

  • Time complexity: O(n2/k)\mathcal{O}(n^2 / k), where nn is a string length. We scan the string no more than n/kn / k times.

  • Space complexity: O(1)\mathcal{O}(1). A copy of a string may be created in some languages, however, the algorithm itself only uses the current string.


Approach 2: Memoise Count

If you observe how the count changes in the approach above, you may have an idea to store it for each character. That way, we do not have to start from the beginning each time we remove a substring. This approach will give us linear time complexity, and the trade-off is the extra memory to store counts.

Algorithm

  1. Initialize counts array of size n.

  2. Iterate through the string:

    • If the current character is the same as the one before, set counts[i] to counts[i - 1] + 1.

      • Otherwise, set counts[i] to 1.
    • If counts[i] equals k, erase last k characters and decrease i by k.

Complexity Analysis

  • Time complexity: O(n)\mathcal{O}(n), where nn is a string length. We process each character in the string once.

  • Space complexity: O(n)\mathcal{O}(n) to store the count for each character.


Approach 3: Stack

Instead of storing counts for each character, we can use a stack. When a character does not match the previous one, we push 1 to the stack. Otherwise, we increment the count on the top of the stack.

Stack Illustration

Algorithm

  1. Iterate through the string:

    • If the current character is the same as the one before, increment the count on the top of the stack.

      • Otherwise, push 1 to the stack.
    • If the count on the top of the stack equals k, erase last k characters and pop from the stack.

Note that, since Integer is immutable in Java, we need to pop the value first, increment it, and then push it back (if it's less than k).

Complexity Analysis

  • Time complexity: O(n)\mathcal{O}(n), where nn is a string length. We process each character in the string once.

  • Space complexity: O(n)\mathcal{O}(n) for the stack.


Approach 4: Stack with Reconstruction

If we store both the count and the character in the stack, we do not have to modify the string. Instead, we can reconstruct the result from characters and counts in the stack.

Algorithm

  1. Iterate through the string:

    • If the current character is the same as on the top of the stack, increment the count.

      • Otherwise, push 1 and the current character to the stack.
    • If the count on the top of the stack equals k, pop from the stack.

  2. Build the result string using characters and counts in the stack.

Complexity Analysis


Approach 5: Two Pointers

This method was proposed by @lee215, and we can use it to optimize string operations in approaches 2 and 3. Here, we copy characters within the same string using the fast and slow pointers. Each time we need to erase k characters, we just move the slow pointer k positions back.

Two Pointers Illustration

Algorithm

  1. Initialize the slow pointer (j) with zero.

  2. Move the fast pointer (i) through the string:

    • Copy s[i] into s[j].

    • If s[j] is the same as s[j - 1], increment the count on the top of the stack.

      • Otherwise, push 1 to the stack.
    • If the count equals k, decrease j by k and pop from the stack.

  3. Return j first characters of the string.

Complexity Analysis

Report Article Issue

Comments: 26
CoderJoe's avatar
Read More

Thank you Leetcode for getting me the job at Bloomberg

244
Show 11 replies
Reply
Share
Report
manmay's avatar
Read More

Using 2 stacks, the solution will become so much intuitive and easy. [Accepted]

  • one stack for holding unique elements let's say (stack)
  • another stack (let say counter_stack) for storing current count from the stack.peek( )
  • Loop through each item in s and adjust/remove top elements of both stacks.
  • build a return string using both of the stacks.
  • Simple Python3 implementation is below.
    def removeDuplicates(s: str, k: int) -> str:
        stack = []
        counter_stack = []
        for val in s:
            if not stack or stack[-1]!=val:
                stack.append(val)
                counter_stack.append(1)
            elif stack[-1]==val:
                counter_stack[-1]+=1
            if counter_stack[-1]==k:
                counter_stack.pop()
                stack.pop()
        return ''.join([stack[i]*counter_stack[i] for i in range(len(stack))])

32
Show 2 replies
Reply
Share
Report
blake-st's avatar
Read More

Just want to point out for some of the solutions, with "sb.delete(i - k + 1, i + 1);", the time complexity won't simply be O(N)..

27
Show 5 replies
Reply
Share
Report
Zizhen_Huang's avatar
Read More

The two pointers are nice

8
Reply
Share
Report
ufdeveloper's avatar
Read More

You can also store an Item{ char c, int count} on the stack and keep popping the stack every time the count is k. At the end, pop the non-empty stack into the result string.

5
Show 2 replies
Reply
Share
Report
Rwq48AIa0Rh9's avatar
Read More

For me, the easiest solution was using 1 stack which holds arrays of the form [c, f] where c is the character and f is the frequency. I've also made a video for anyone looking for a more thorough explanation! :) Happy studying all!

https://www.youtube.com/watch?v=Rq4-1LonjaQ

class Solution:
    def removeDuplicates(self, s, k):
        #[['c1', n1], ['c2', n2], ...]
        stack = []
        
        for c in s:
            if stack and stack[-1][0] == c:
                stack[-1][1] += 1
                if stack[-1][1] >= k:
                    stack.pop()
            else:
                stack.append([c, 1])
        
        result = ''
        for arr in stack:
            result += (arr[0] * arr[1])
        
        return result

2
Reply
Share
Report
jaspier's avatar
Read More

I think answers with stacks probably would be more than O(n), since you may have to remove k elements a certain m amount of times. It would be something like O(n + (km)). Any thoughts on that?

2
Show 1 reply
Reply
Share
Report
dogenzen's avatar
Read More

The Simplest solution is not mentioned :-)

credit https://leetcode.com/fishercoder/

   public String removeDuplicates(String s, int k) {
        char last = ' ';
        int count = 1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            if (c == last) count++;
            else count = 1;
            
            if (count == k)
                s = removeDuplicates(s.substring(0, i-k+1) + s.substring(i+1), k);
            
            last = c;    
        }
        
        return s;
    }

3
Show 1 reply
Reply
Share
Report
anoncitizen4anarchy's avatar
Read More

is approach 2 considered dynamic programming?

2
Reply
Share
Report
mykhol1995's avatar
Read More

Why can't we use StringBuilder as stack (and sb.setLength to "remove" characters)? When we do "remove" we have to go from the end and count number of "written" characters. But it can happen not more than n/k times and we read no more than k chars, so it's O(N) for time and O(1) for additional space (but O(N) for string that we should return). So, we don't allocate space for stacks/arrays. Do I miss something? I implemented this and reached 98% for time (3ms) and 97.3% for space (38.7MB)

1
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
05/06/2021 08:42Accepted16 ms10.9 MBcpp
05/06/2021 08:41Accepted16 ms10.9 MBcpp
04/16/2021 17:18Accepted8 ms8.7 MBcpp
/37
Contribute
|||
Saved
Trie
This list is empty.